public class MyQueue {
    // 定义双向链表节点类
    static class ListNode {
        public int value;    // 节点存储的值
        public ListNode next; // 指向下一个节点的指针
        public ListNode prev; // 指向前一个节点的指针

        public ListNode(int value) {
            this.value = value;
        }
    }

    public ListNode first;  // 队头指针
    public ListNode last;   // 队尾指针
    public int usedSize;    // 队列当前元素个数

    /**
     * 入队操作,向双向链表位置插入新节点（尾插法）
     * @param val 要插入的值
     */
    public void offer(int val) {
        ListNode node = new ListNode(val); // 创建新节点
        if(first == null) { // 如果队列为空
            first = last = node; // 队头和队尾都指向新节点
            usedSize++; // 增加队列大小
            return;
        }
        // 队列不为空的情况
        last.next = node; // 当前队尾的next指向新节点
        node.prev = last; // 新节点的prev指向当前队尾
        last = node;      // 更新队尾指针为新节点
        usedSize++;       // 增加队列大小
    }

    /**
     * 出队操作，将双向链表头节点删除掉（删除队头元素）
     * @return 被删除的元素值，如果队列为空返回-1
     */
    public int poll() {
        // 1. 队列为空
        // 2. 正常删头节点先first = first.next;跳过头节点然后把first.prev = null;
        // 但是发现有特殊情况队列中只有一个元素/链表中只有一个节点
        // 解决方式就直接将队尾指针置空first = null，因为前面first = first.next;操作队头就为null了
        if(first == null) { // 队列为空
            return -1;
        }
        int oldValue = first.value; // 保存队头元素值
        first = first.next; // 移动队头指针到下一个节点

        if(first == null) { // 如果队列中只有一个元素的情况
            last = null;   // 队尾指针也需要置空
        } else {
            first.prev = null; // 断开新队头的前驱指针
        }
        usedSize--; // 减少队列大小
        return oldValue; // 返回被删除的元素值
    }

    /**
     * 获取队头元素但不删除
     * @return 队头元素值，如果队列为空返回-1
     */
    public int peek() {
        if(first == null) { // 队列为空
            return -1;
        }
        return first.value; // 返回队头元素值
    }

    /**
     * 获取队列大小
     * @return 队列中元素个数
     */
    public int size() {
        return usedSize;
    }

    /**
     * 判断队列是否为空
     * @return true表示队列为空，false表示不为空
     */
    public boolean isEmpty() {
        return usedSize == 0;
    }

}
